%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass{article}

\usepackage{subfigure}
\usepackage{tikz}
\usepackage{tkz-berge}  %% for drawing combinatorial graphs
\usetikzlibrary{external}
\tikzexternalize{Prim-algorithm-undirected-graph}

\begin{document}

\begin{figure}
\subfigure[Original undirected graph.]{
\begin{tikzpicture}
[lineDecorate/.style={-,thick},%
  nodeDecorate/.style={shape=circle,inner sep=1.5pt,draw,thick},%
  scale=0.8]
\scriptsize
%% nodes or vertices
\foreach \nodename/\x/\y in {
  0/0/0, 1/3/1.5, 2/6/3, 3/0/3, 4/3/4.5, 5/0/6, 6/3/7.5}
{
  \node (\nodename) at (\x,\y) [nodeDecorate] {\scriptsize$\nodename$};
}
%% edges or lines
\tikzstyle{EdgeStyle}=[-,thick]
\tikzstyle{LabelStyle}=[fill=white]
\foreach \startnode/\endnode/\weight in {
  0/1/7, 0/3/5, 1/2/8, 1/3/9, 1/4/7, 2/4/5, 3/4/15, 3/5/6, 4/5/8,
  4/6/9, 5/6/11}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
\end{tikzpicture}
}
%%
%%
\qquad
\subfigure[1st iteration of while loop.]{
\begin{tikzpicture}
[lineDecorate/.style={-,thick},%
  nodeDecorate/.style={shape=circle,inner sep=1.5pt,draw,thick},%
  scale=0.8]
\scriptsize
%% nodes or vertices
\foreach \nodename/\x/\y in {
  0/0/0, 1/3/1.5, 2/6/3, 3/0/3, 4/3/4.5, 5/0/6, 6/3/7.5}
{
  \node (\nodename) at (\x,\y) [nodeDecorate] {\scriptsize$\nodename$};
}
%% light edges or lines
\tikzstyle{EdgeStyle}=[-,thick,color=gray!30]
\tikzstyle{LabelStyle}=[fill=white]
\foreach \startnode/\endnode/\weight in {
  0/1/7, 0/3/5, 1/2/8, 1/3/9, 1/4/7, 2/4/5, 3/4/15, 4/6/9}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
%% dark edges or lines
\tikzstyle{EdgeStyle}=[-,thick]
\foreach \startnode/\endnode/\weight in {3/5/6, 4/5/8, 5/6/11}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
\end{tikzpicture}
}
%%
%%
\subfigure[2nd iteration of while loop.]{
\begin{tikzpicture}
[lineDecorate/.style={-,thick},%
  nodeDecorate/.style={shape=circle,inner sep=1.5pt,draw,thick},%
  scale=0.8]
\scriptsize
%% nodes or vertices
\foreach \nodename/\x/\y in {
  0/0/0, 1/3/1.5, 2/6/3, 3/0/3, 4/3/4.5, 5/0/6, 6/3/7.5}
{
  \node (\nodename) at (\x,\y) [nodeDecorate] {\scriptsize$\nodename$};
}
%% light edges or lines
\tikzstyle{EdgeStyle}=[-,thick,color=gray!30]
\tikzstyle{LabelStyle}=[fill=white]
\foreach \startnode/\endnode/\weight in {
  0/1/7, 1/2/8, 1/3/9, 1/4/7, 2/4/5, 3/4/15, 4/6/9}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
%% dark edges or lines
\tikzstyle{EdgeStyle}=[-,thick]
\foreach \startnode/\endnode/\weight in {0/3/5, 1/3/9, 3/5/6, 4/5/8, 5/6/11}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
\end{tikzpicture}
}
%%
%%
\qquad
\subfigure[3rd iteration of while loop.]{
\begin{tikzpicture}
[lineDecorate/.style={-,thick},%
  nodeDecorate/.style={shape=circle,inner sep=1.5pt,draw,thick},%
  scale=0.8]
\scriptsize
%% nodes or vertices
\foreach \nodename/\x/\y in {
  0/0/0, 1/3/1.5, 2/6/3, 3/0/3, 4/3/4.5, 5/0/6, 6/3/7.5}
{
  \node (\nodename) at (\x,\y) [nodeDecorate] {\scriptsize$\nodename$};
}
%% light edges or lines
\tikzstyle{EdgeStyle}=[-,thick,color=gray!30]
\tikzstyle{LabelStyle}=[fill=white]
\foreach \startnode/\endnode/\weight in {
  1/2/8, 1/3/9, 1/4/7, 2/4/5, 3/4/15, 4/6/9}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
%% dark edges or lines
\tikzstyle{EdgeStyle}=[-,thick]
\foreach \startnode/\endnode/\weight in {0/1/7, 0/3/5, 3/5/6, 4/5/8, 5/6/11}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
\end{tikzpicture}
}
%%
%%
\subfigure[4th iteration of while loop.]{
\begin{tikzpicture}
[lineDecorate/.style={-,thick},%
  nodeDecorate/.style={shape=circle,inner sep=1.5pt,draw,thick},%
  scale=0.8]
\scriptsize
%% nodes or vertices
\foreach \nodename/\x/\y in {
  0/0/0, 1/3/1.5, 2/6/3, 3/0/3, 4/3/4.5, 5/0/6, 6/3/7.5}
{
  \node (\nodename) at (\x,\y) [nodeDecorate] {\scriptsize$\nodename$};
}
%% light edges or lines
\tikzstyle{EdgeStyle}=[-,thick,color=gray!30]
\tikzstyle{LabelStyle}=[fill=white]
\foreach \startnode/\endnode/\weight in {1/3/9, 2/4/5, 3/4/15, 4/5/8, 4/6/9}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
%% dark edges or lines
\tikzstyle{EdgeStyle}=[-,thick]
\foreach \startnode/\endnode/\weight in {
  0/1/7, 0/3/5, 1/2/8, 1/4/7, 3/5/6, 5/6/11}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
\end{tikzpicture}
}
%%
%%
\qquad
\subfigure[Final MST.]{
\begin{tikzpicture}
[lineDecorate/.style={-,thick},%
  nodeDecorate/.style={shape=circle,inner sep=1.5pt,draw,thick},%
  scale=0.8]
\scriptsize
%% nodes or vertices
\foreach \nodename/\x/\y in {
  0/0/0, 1/3/1.5, 2/6/3, 3/0/3, 4/3/4.5, 5/0/6, 6/3/7.5}
{
  \node (\nodename) at (\x,\y) [nodeDecorate] {\scriptsize$\nodename$};
}
%% edges or lines
\tikzstyle{EdgeStyle}=[-,thick]
\tikzstyle{LabelStyle}=[fill=white]
\foreach \startnode/\endnode/\weight in {
  0/1/7, 1/4/7, 3/0/5, 4/2/5, 4/6/9, 5/3/6}
{
  \Edge[label=$\weight$](\startnode)(\endnode)
}
\end{tikzpicture}
}
\end{figure}

\end{document}
